/**
 * quadtree-rs
 * @version 1.2.3
 * @license MIT
 * @Author Timo Hausmann
 */

/* https://github.com/timohausmann/quadtree-js.git v1.2.3 */

/**
 * @Author lianbo
 * @date 2020-11-11 20:33:13
 * @Description:
 *                    .(x,y)     *
 *                       1       *     0
 *                               *
 *                 ****************************->x
 *                               *
 *                       2       *     3
 *                               *
 *                               *
 *                              ﹀ Y
 * 四叉树的位置区分
 *
 */
pub struct Quadtree {
    pub max_objects: i32,
    pub max_levels: i32,
    pub level: i32,
    pub bounds: Bounds,
    pub objects: Vec<Bounds>,
    pub nodes: Vec<Quadtree>,
}

#[derive(Clone, Debug, Copy, PartialEq)]
pub struct Bounds {
    pub x: f64,
    pub y: f64,
    pub width: f64,
    pub height: f64,
}

impl Quadtree {
    /**
     * Quadtree Constructor
     * @param  bounds            bounds of the node { x, y, width, height }
     * @param  max_objects      (optional) max objects a node can hold before splitting into 4 subnodes (default: 10)
     * @param  max_levels       (optional) total max levels inside root Quadtree (default: 4)
     * @param  level            (optional) depth level, required for subnodes (default: 0)
     */
    pub fn new(bounds: Bounds, max_objects: i32, max_levels: i32, level: i32) -> Quadtree {
        Quadtree {
            max_objects: max_objects,
            max_levels: max_levels,
            level: level,
            bounds: bounds,
            objects: Vec::new(),
            nodes: Vec::new(),
        }
    }

    /**
     * Split the node into 4 subnodes
     */
    pub fn split(&mut self) {
        let next_level = self.level + 1;
        let sub_width = self.bounds.width / 2.0;
        let sub_height = self.bounds.height / 2.0;
        let x = self.bounds.x;
        let y = self.bounds.y;

        //top right node
        self.nodes.push(Quadtree::new(
            Bounds {
                x: x + sub_width,
                y: y,
                width: sub_width,
                height: sub_height,
            },
            self.max_objects,
            self.max_levels,
            next_level,
        ));

        //top left node
        self.nodes.push(Quadtree::new(
            Bounds {
                x: x,
                y: y,
                width: sub_width,
                height: sub_height,
            },
            self.max_objects,
            self.max_levels,
            next_level,
        ));

        //bottom left node
        self.nodes.push(Quadtree::new(
            Bounds {
                x: x,
                y: y + sub_height,
                width: sub_width,
                height: sub_height,
            },
            self.max_objects,
            self.max_levels,
            next_level,
        ));

        //bottom right node
        self.nodes.push(Quadtree::new(
            Bounds {
                x: x + sub_width,
                y: y + sub_height,
                width: sub_width,
                height: sub_height,
            },
            self.max_objects,
            self.max_levels,
            next_level,
        ));
    }

    /**
     * Determine which node the object belongs to
     * @param  pRect      bounds of the area to be checked, with x, y, width, height
     * @return Array            an array of indexes of the intersecting subnodes
     *                          (0-3 = top-right, top-left, bottom-left, bottom-right / ne, nw, sw, se)
     *                          原版没有将分割线计算在内
     */
    pub fn get_index(&self, p_rect: &Bounds) -> Vec<usize> {
        let mut indexes = Vec::new();
        let vertical_midpoint = self.bounds.x + self.bounds.width / 2.0;
        let horizontal_midpoint = self.bounds.y + self.bounds.height / 2.0;

        let start_is_north = p_rect.y < horizontal_midpoint;
        let start_is_west = p_rect.x < vertical_midpoint;
        let end_is_north = p_rect.y + p_rect.height < horizontal_midpoint;
        let end_is_west = p_rect.x + p_rect.width < vertical_midpoint;
        let start_is_south = !start_is_north;
        let start_is_east = !start_is_west;

        if end_is_west {
            if end_is_north {
                indexes.push(1);
                return indexes;
            } else {
                if start_is_south {
                    indexes.push(2);
                    return indexes;
                } else {
                    indexes.push(1);
                    indexes.push(2);
                    return indexes;
                }
            }
        } else {
            if start_is_east {
                if start_is_south {
                    indexes.push(3);
                    return indexes;
                } else {
                    if end_is_north {
                        indexes.push(0);
                        return indexes;
                    } else {
                        indexes.push(0);
                        indexes.push(3);
                        return indexes;
                    }
                }
            } else {
                if start_is_south {
                    indexes.push(2);
                    indexes.push(3);
                    return indexes;
                } else {
                    if (end_is_north) {
                        indexes.push(0);
                        indexes.push(1);
                        return indexes;
                    } else {
                        indexes.push(0);
                        indexes.push(1);
                        indexes.push(2);
                        indexes.push(3);
                        return indexes;
                    }
                }
            }
        }
    }

    /**
     * Insert the object into the node. If the node
     * exceeds the capacity, it will split and add all
     * objects to their corresponding subnodes.
     * @param  pRect        bounds of the object to be added { x, y, width, height }
     */
    pub fn insert(&mut self, p_rect: Bounds) {
        let mut indexes = Vec::new();

        //if we have subnodes, call insert on matching subnodes
        if !self.nodes.is_empty() {
            indexes = self.get_index(&p_rect);

            for i in 0..indexes.len() {
                self.nodes[indexes[i]].insert(p_rect);
            }
            return;
        }

        //otherwise, store object here
        self.objects.push(p_rect);

        //max_objects reached
        if self.objects.len() > self.max_objects as usize && self.level < self.max_levels {
            //split if we don't already have subnodes
            if self.nodes.is_empty() {
                self.split();
            }

            //add all objects to their corresponding subnode
            for i in 0..self.objects.len() {
                indexes = self.get_index(&self.objects[i]);
                for k in 0..indexes.len() {
                    self.nodes[indexes[k]].insert(self.objects[i]);
                }
            }

            //clean up this node
            self.objects = Vec::new();
        }
    }

    /**
     * Return all objects that could collide with the given object
     * @param  pRect      bounds of the object to be checked { x, y, width, height }
     * @return Array            array with all detected objects
     */
    pub fn retrieve(&self, p_rect: &Bounds) -> Vec<Bounds> {
        let mut indexes = self.get_index(p_rect);
        let mut return_objects = self.objects.clone();

        //if we have subnodes, retrieve their objects
        if !self.nodes.is_empty() {
            for i in 0..indexes.len() {
                return_objects.append(&mut self.nodes[indexes[i]].retrieve(p_rect));
            }
        }

        //remove duplicates
        return_objects.dedup();

        return return_objects;
    }

    /**
     * Clear the quadtree
     */
    pub fn clear(&mut self) {
        self.objects = Vec::new();

        for i in 0..self.nodes.len() {
            if !self.nodes.is_empty() {
                self.nodes[i].clear();
            }
        }
        self.nodes = Vec::new();
    }
}
